package com.singzi.leetcode.N800;

/**
 * 给两个整数数组 A 和 B
 * 返回两个数组中公共的、长度最长的子数组的长度。
 *
 * 动态规划
 */
public class T0718 {
    public static void main(String[] args) {
        Solution0718 solution0718 = new Solution0718();
        int[]A = {1,2,3,2,1};
        int[]B= {3,2,1,4,7};
        System.out.println(solution0718.findLength(A, B));


    }
}
class Solution0718{
    public int findLength(int[]A,int[]B){
        if(A.length == 0||B.length ==0){
            return 0;
        }
        int[][]dp = new int[A.length+1][B.length+1];
        int result = 0;
        for (int i = 1; i <=A.length; i++) {
            for (int j = 1; j <=B.length; j++) {
                if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(dp[i][j]>result){
                        result = dp[i][j];
                    }
                }
            }

        }
        return result;
    }
}
